package com.arron.algorithm.leetcodetop100.二分查找;

import java.util.HashSet;
import java.util.Set;

/**
 *  Leetcode 287. 寻找重复数
 *    中等难度
 */
public class 寻找重复数 {


    /**
     * 使用额外空间 hash表
     * @param nums
     * @return
     */
    public static int findDuplicate(int[] nums) {

        Set<Integer> integerSet = new HashSet<>();

        for (int i : nums) {
            if (integerSet.contains(i)){
                return i;
            }else {
                integerSet.add(i);
            }
        }
        return -1;
    }


    /**
     * 暴力解法 时间会超时
     * @param nums
     * @return
     */
    public static int findDuplicate2(int[] nums) {



        for (int i = 0; i < nums.length; i++) {
            int count = 0;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) count += 1;
            }
            if (count > 0) return nums[i];
        }
        return -1;
    }





    /**
     *
     *   '''2、小于O(n^2) 二分查找
     *         我们不要考虑数组,只需要考虑 数字都在 1 到 n 之间
     *         示例 1:
     *         arr = [1,3,4,2,2] 此时数字在 1 — 5 之间
     *
     *         mid = (1 + 5) / 2 = 3 arr小于等于的3有4个(1,2,2,3)，1到3中肯定有重复的值
     *         mid = (1 + 3) / 2 = 2 arr小于等于的2有3个(1,2,2)，1到2中肯定有重复的值
     *         mid = (1 + 2) / 2 = 1 arr小于等于的1有1个(1)，2到2中肯定有重复的值
     * 2 分法
     * @param nums
     * @return
     */
    public static int findDuplicate3(int[] nums) {

        int left = 1;
        int right = nums.length;
        int cnt = 0;
        while (left<right) {
            cnt = 0;
            int mid = left + (right - left) / 2;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] <= mid) {
                    cnt++;
                }
            }

            if (cnt > mid) {
                right = mid;
            } else {
                left = mid+1;
            }
        }
        return  left;
    }

    public static void main(String[] args) {
        int nums[] = {1,3,4,2,2};
        System.out.println(findDuplicate3(nums));

    }



}
